package com.guchenbo.example.lock;

import java.util.Arrays;

/**
 * @author guchenbo
 * @date 2022/3/23
 */
public class Tmp {
    public static void main(String[] args) {
        Tmp tmp = new Tmp();
        String s = "dcce";
        System.out.println(tmp.f(s));
        String[] queries = new String[] { "cbd" };
        String[] words = new String[] { "zaaaz" };
        System.out.println(Arrays.toString(tmp.numSmallerByFrequency(queries, words)));
    }
    public int[] numSmallerByFrequency(String[] queries, String[] words) {

        int[] answer=new int[queries.length];
        int[] queries2=new int[queries.length];
        int[] words2=new int[words.length];

        for(int i=0;i<queries.length;i++){
            queries2[i]=f(queries[i]);
        }
        for(int i=0;i<words.length;i++){
            words2[i]=f(words[i]);
        }
        Arrays.sort(words2);
        for(int i=0;i<queries2.length;i++){
            //小于target的最大长度
            int cnt=bicnt(words2,queries2[i]);
            answer[i]=cnt;
        }
        return answer;
    }

    public int bicnt(int[] nums,int target){
        int l=0;
        int r=nums.length-1;
        int ret=-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]<target){
                ret=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return ret+1;
    }
    public int f(String s){
        char min = 'z'+1;
        int cnt=0;
        for(int i=0;i<s.length();i++){
            if (s.charAt(i)==min){
                cnt++;
            }else if(s.charAt(i)<min){
                cnt=1;
                min=s.charAt(i);
            }
        }
        return cnt;
    }
}
